Commentary by cpressey on Formal Language works =============================================== ### Introduction to Formal Languages A decent older textbook on formal languages. ### Natural Language Processing Techniques in Prolog Some introduction to DCGs and chart parsing and feature structures. ### Programs, Grammars, Arguments ### The Hardest Context-Free Language It's CFL-complete, for any reasonable conception of "CFL-complete". ### Lecture 7: Definite Clause Grammars ### On the Structure of Context-Sensitive Grammars Interesting technical report on (and this is the author's phrasing, not mine) "what context gets you". It's like a Turing machine, but in some ways worse. It doesn't just have to launch the tape head flying down the tape until it reaches some area of interest (a global variable, say); it actually has to launch _symbols_ across the input string, sliding them along like "messages", until they interact with whatever we wanted them to interact with. In this way, it's also a lot like a 1D cellular automaton. ### Functional Unification Grammar ### Definite Clause Grammars for Language Analysis ### Formal Languages and Infinite Groups An exposition of formal language theory from the perspective of group theory, giving an algebraic formulation of the usual classes of formal languages. ### Formal languages and groups as memory Explores an interesting twist on "counter automata" where the "counter" is not an integer, but only an algebraic structure with (some of) the properties of an integer: a group or a monoid. ### Is there a reasonable and studied concept of reduction between regular languages? ### Representing \"but not\" in formal grammar ### Proving that a word is \*not\* generated by a context-free grammar ### Does there exist an context free language L such that L∩L\^R is not context free? ### Context-free complete language ### Natural examples of context-sensitive languages from practice ### Is \"regex\" in modern programming languages really \"context sensitive grammar\"?